package newcoder_exp.justPractise;

import java.util.Arrays;

import org.junit.Test;
import java.util.*;

public class Ex92 {

    public class Solution {
        /**
         * longest common subsequence
         * 
         * @param s1 string字符串 the string
         * @param s2 string字符串 the string
         * @return string字符串
         */
        public String LCS(String s1, String s2) {
            if (s1 == null || s2 == null)
                return "-1";
            int len1 = s1.length(), len2 = s2.length();
            if (len1 == 0 || len2 == 0)
                return "-1";

            int[][] f = new int[len1][len2];

            for (int i = 0; i < len1; i++) {
                for (int j = 0; j < len2; j++) {
                    if (i == 0 && j == 0) {
                        f[i][j] = s1.charAt(0) == s2.charAt(0) ? 1 : 0;
                    } else if (i == 0) {
                        f[i][j] = f[0][j - 1];
                        if (f[i][j] == 0 && s1.charAt(i) == s2.charAt(j)) {
                            f[i][j] = 1;
                        }
                    } else if (j == 0) {
                        f[i][j] = f[i - 1][0];
                        if (f[i][j] == 0 && s1.charAt(i) == s2.charAt(j)) {
                            f[i][j] = 1;
                        }
                    } else {
                        f[i][j] = f[i - 1][j - 1];
                        if (s1.charAt(i) == s2.charAt(j)) {
                            f[i][j] += 1;
                        }
                        f[i][j] = Math.max(f[i][j], Math.max(f[i - 1][j], f[i][j - 1]));
                    }
                }
            }

            if (f[len1 - 1][len2 - 1] == 0)
                return "-1";

            Stack<Character> stack = new Stack<>();
            // Stack<Character> stack2 = new Stack<>();
            int i = len1 - 1, j = len2 - 1;
            while (i > 0 && j > 0) {
                if (f[i][j] == f[i - 1][j - 1]) {
                    i--;
                    j--;
                } else if (f[i][j] == f[i - 1][j]) {
                    i--;
                } else if (f[i][j] == f[i][j - 1]) {
                    j--;
                } else {
                    stack.push(s1.charAt(i));
                    i--;
                    j--;
                }
            }
            if (f[i][j] > 0) {
                if (i == 0) stack.push(s1.charAt(0));
                else stack.push(s2.charAt(0));
            }
                
            StringBuilder sb = new StringBuilder();
            while (!stack.isEmpty()) {
                sb.append(stack.pop());
            }
            return sb.toString();
        }
    }

    @Test
    public void test() {
        String s1 = "EKhHnp06qE75TmA7036PyZdlzad49gGNsEAe0830ozh5zKD1w3ngrA7VA0OvK15v12WzqDERP375C3NJKP934O8Ix0NF412B6Kk2hbALBzYFq66r0BuSPt1KD816nwOWB0M1dK2Cg1s9O6IfQTS0bT852U78SSjk4astw2KKvudmsavy2699Ut1DN3bp0cbJuB131j6W8L7NTf8NnfznSWtF7g3UDB9O68UXU730f02WLnPGCcHOn0SRnnuXrQ862Z77Jo24H3WAmEZG5BbKztIec1OFr7kXS54k1HBN5Mqx5f6SzL6Po3LDXmIlb613ZBozxg5c9Uc3Bnssp17E1ch2ZS5LGn4TYf2CN88J2GC43k12hV4zeg23S4D3LNM31R6R3JuoMDBwHc349pzjmb7nCxWysf9csh4vC30k5185H023UI6E2Eiwys8bhb97CoDv16X40iNgb89O0c2C4y0Ew0FoHSFyePi34s2ik9H5KFgD7aCbar29j2bNxGo7ym1xO5VQouJAhmAZhBVHF6QPspcvn90zH8B2928Lae8a6JD28z38Z56Urr1MB8753xi5NfdGqA5CekTU0MStGmDBOzTE0GAfc3ygNLLTe0rwQ2WN4rX62YiwOBkX3OUJt8IR2Z7xv6u3g0E3498072lOGX6nm6zQJsV38HN4IFL9ekbWdMEr904wkK4mbEjz0ff3NB7G1x4Q42o9X2Vj5kDuSFl7HOT8CyMzw18kVoiDj3ri0EB2zl585M93rdOlcXL1acrR4m1VmRNRkj6YOsxa7g841UG77T5e2N61iZ1375A9BMKj5Li15rNKR33dXU6dNASuEBTgL4IR347M6kK40L6ui7uLW64qIUpPZvy5s3LP9827FWJEH98aB68rhp8xqUhJ6VPv4HJudP1l5wwL7g2B2o9s9P377Ed4c24e5HmDs5RU8YbB9uCGHC5da081o4C26FhJR8NSe0tIKoHPgbq31zNEmDo1nF3l1O4aSy0LF9dfthJFy0nWzyMdCy6du3bRNF8z93MKF1bJbehe16cqHXqFJI54aE3K9h8pooBgSqG4U9FH2eZT3IB21RJH24e9lrGpE8l22WOB3WmMj806890C45Few54gN5F1jBO2Ge5KqSopHaqK2FkvVStbeFkz4p143709gLtwIiww9E2Eg9VPty7Jx7ej7nmW5rfpnfwXWiD6zNg9z7J2ybs96l23868bytw8cA0H2kAA1QOidYvrA255bAZt0x5GTIrOP5I0ynCRsT54MYiDgFkJX7I7X9F2K3n369GOl8Ih3w7vwpq4f214e2l0745K9ighL6Pz7PNCO8oP5YNQ3oHXK7HV82bUSPk19kwu8xRRp8mNBAeo2W7yMe64UQD6W95fFo1NS2Q49e958w493WVL3O2t98Au6P3z3Bifb2bmQL1GXcL9VT1X3EgnmvnN03yqGVt278KLL5rJv05U7GUFOi957m8UFn5156Bg9ZcC9OM4Y2jdI1590XO9SrOF222gG13fP9WCNZ47298lZKA5h4sA20pyDqao3PP5YCCcIfTvsYy2ZR5w93s4Y8j0as32gy0ItXOzpqyp7hzik9P958hh8rEULpx1q63bo51Y3s8jLpCusP7O34REDjmixA2s2i4wbcVVshrvio1E4dJB77r2X6J3j8oW6LfmDuDpy3xy5wnJzAwjS5T78", s2 = "kQlReRfFX";
        Solution s = new Solution();
        System.out.println(s.LCS(s1, s2));
    }
}
